/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package domain;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.Iterator;
/**
 *
 * @author Sandra del Moral Lazo, Jose Villaverde Garcia
 */
public class TestDictionary extends Dictionary implements Serializable{

    //Attributes
    private Trie<Matrix> _dictionary;
    private int _numofwords;
    //Associations
    private Model _model;
    private class Matrix {

    }

    protected TestDictionary(Model model) {
        _dictionary = new Trie<Matrix>();
        _numofwords = 0;
        _model = model;
    }

    /**
     * Genera una llista de totes les possibles alphas agafant totes les
     * subseqüències de correctword cw: [(cw.tamany - i) .. cw.tamany]
     * on i va de 0 fins a S, on S es N si N és més petit que cw.tamany
     * i cw.tamany altrament
     *
     * @param N és el tamany màxim que pot ser alpha
     * @param correctword és la paraula correcta
     * @return una llista de String amb totes les possibles subseqüències
     */
    private ArrayList<String> getAlphas(int N ,String correctword) {
        int start;
        ArrayList<String> omegas = new ArrayList<String>();
        if(N > correctword.length()) start = correctword.length();
        else {
            int si = correctword.length();
            correctword = correctword.substring(si-Constants.getN(), si);
            start = N;
        }
        for(int i = start-1; i >= 0; --i) {
            String newsubstring;
            newsubstring = correctword.substring(i, start);
            omegas.add(newsubstring);
        }
        return omegas;
    }

    /**
     * Genera una llista de totes les possibles betas agafant totes les
     * subseqüències d'incorrectword iw:  [(iw.tamany - i) .. iw.tamany] de iw,
     * on i va de 0 fins a iw.tamany.
     *
     * @param incorrectword és la paraula incorrecta
     * @return una llista de String amb totes les possibles subseqüències
     * d'incorrectword
     */
    private ArrayList<String> getBetas(String incorrectword) {
        String beta = "";
        ArrayList<String> betas = new ArrayList<String>();
        betas.clear();
        for(int i = incorrectword.length(); i >= 0; --i ) {
            beta = incorrectword.substring(i, incorrectword.length());
            betas.add(beta);
        }
        return betas;
    }

    /**
     * Cerca tots els possibles parells de normes alpha->beta i es guarda la
     * màxima probabilitat i les normes les quals han servit per arribar a
     * aquest màxim a la matrixtemp i la matrixpair respectivament
     *
     * @param N és el tamany màxim que pot ser alpha
     * @param incorrectword és la paraula incorrecta
     * @param alphas és una llista d'String amb totes les possibles alpha que
     * es pot obtenir a partir de la paraula correcta
     * @param betas és una llista d'String amb totes les possibles beta que
     * es pot obtenir a partir de la paraula incorrecta
     * @param matrixtemp és una matriu amb les probabilitats anteriors que s'usa
     * per aumentar l'eficiéncia del programa de forma dinàmica
     * @param matrixpair és una matriu amb les normes de alpha a betas
     * anteriors que s'usa per aumentar l'eficiéncia del programa de forma
     * dinàmica
     */
    private void matrixsProbability(int N, String incorrectword, ArrayList<String> alphas, ArrayList<String> betas, float matrixtemp[][], Element[][]  matrixpair) {
        //S'inicialitza les variables
        String alpha,beta;
        alpha = "";
        boolean have_max = false;
        Pair<String, String> rule = new Pair<String, String> ();
        rule.first = "";
        rule.second = "";
        float MAX = (float)0;
        //Per a cada beta es mira quina alpha més adequada per canviar, és a dir,
        //es busca el substring alpha més probable de ser canviat pel substring beta
        for(int i = 0; i < betas.size(); ++i) {
            beta = betas.get(i);
            for(int j = 0; j < alphas.size(); ++j) {
                alpha = alphas.get(j);
                //Es crida a Model per mirar quina es la probabilitat
                float f = _model.getProbability(alpha, beta);
                //Es comprova que la alpha i beta donades estiguin dintre dels paràmetres
                if(incorrectword.length()-beta.length() >= 0 && N-alpha.length() >= 0) {
                    //Es multiplica la probababilitat d'aquest canvi amb els seus anteriors
                    f*=matrixtemp[incorrectword.length()-beta.length()][N-alpha.length()];
                    //Si aquest canvi és màxim es guarda
                    if(f > MAX) {
                        MAX = f;
                        rule.first = alpha;
                        rule.second = beta;
                        have_max = true;
                    }
                }
            }
        }
        //Si ha trobat un màxim s'introdueix a la matriu de probabilitats aquests màxim
        //Es guarda a la matriu de normes l'actual d'aquest màxim (alpha->beta) més totes
        //les normes les quals s'han usat per arribat a aquest màxim
        if(have_max) {
            matrixtemp[incorrectword.length()][N] = MAX;
            ArrayList<Pair <String, String> > rules = new ArrayList<Pair <String, String> >();
            rules.addAll(matrixpair[incorrectword.length()-rule.second.length()][N-rule.first.length()].getParam());
            rules.add(rule);
            matrixpair[incorrectword.length()][N].setParam(rules);
        }
    }


    /**
     * Aquesta funció recorre tot el diccionari buscant les paraules correctes
     * més probables per sustituir la paraula incorrecta mitjançant les normes
     *
     * @param current és el diccionari el qual conté paraules i sobre el qual
     * es navega mitjançant les normes (alpha->beta) per trobar paraules
     * correctes compatibles probablement amb la paraula incorrecta
     * @param incorrectword és la paraula incorrecta
     * @param N és el tamany màxim que pot ser alpha
     * @param correctword és la paraula correcta
     * @param matrixtemp és una matriu amb les probabilitats anteriors que s'usa
     * per aumentar l'eficiéncia del programa de forma dinàmica
     * @param matrixpair és una matriu amb les normes de alpha a betas
     * anteriors que s'usa per aumentar l'eficiéncia del programa de forma
     * dinàmica
     * @return una llista de Three que conté totes les possibles paraules
     * correctes que poden substituir la paraula incorrecta amb la seva
     * probabilitat i les seves normes
     */
    private ArrayList<Three<String, Float, ArrayList<Pair<String, String>>>> getCorrect(Trie<Matrix> current, String incorrectword, int N, String correctword, float matrixtemp[][], Element[][]  matrixpair) {
        //S'inicialitza variables
        ArrayList<Three<String, Float, ArrayList<Pair<String, String> > > > wordprob = new ArrayList<Three<String, Float, ArrayList<Pair<String, String>>>>();
        ArrayList<Three<String, Float, ArrayList<Pair<String, String>>>> auxiliar = new ArrayList<Three<String, Float, ArrayList<Pair<String, String>>>>();
        ArrayList<Pair<String, String> > arrstr2 = new ArrayList<Pair<String, String> >();
        Three<String, Float, ArrayList<Pair<String, String>>> triplet = new Three<String, Float, ArrayList<Pair<String, String>>>();
        float accumulator = 0;
        //Agafem el substring del node del diccionari actual i ho concatena amb la paraula correcta que es porta
        String substring = current.getLabel();
        correctword = correctword.concat(substring);
        //Cas que el tamany del String de la paraula correctword sigui més petit que N
        //És el cas que si podem fer substrings de correctword fins a tamany N no es podrien
        //fer degut a que correctword no és suficientment gran
        if(correctword.length() < N){
            //Cas de la primera iteració de l'execució on la paraula correcta és el cas buit
            if (correctword.length()==0) {
                ArrayList<String> alphas =new ArrayList<String>();
                String palabra;
                alphas.add("");
                for (int i = 1; i <= incorrectword.length(); ++i) {
                    palabra = incorrectword.substring(0, i);
                    ArrayList<String> betas =new ArrayList<String>();
                    betas = getBetas(palabra);
                    matrixsProbability(N, palabra, alphas, betas, matrixtemp, matrixpair);
                    matrixtemp[0][N] = _model.getProbability("", "");
                    betas.clear();
                }
                Pair <String, String> rule = new Pair <String, String>();
                rule.first = "";
                rule.second = "";
                ArrayList<Pair <String, String> > rules = new ArrayList<Pair <String, String> >();
                rules.add(rule);
                matrixpair[0][N].setParam(rules);
            }
            //Cas que no és la primera iteració
            else {
                ArrayList<String> alphas =new ArrayList<String>();
                ArrayList<String> betas =new ArrayList<String>();
                alphas = getAlphas(N,correctword);
                betas.add("");
                String palabra;
                for (int i = 1; i <= incorrectword.length(); ++i) {
                    palabra = incorrectword.substring(0, i);
                    matrixsProbability(N, palabra, alphas, betas, matrixtemp, matrixpair);
                    betas = getBetas(palabra);
                    matrixsProbability(N, palabra, alphas, betas, matrixtemp, matrixpair);
                    betas.clear();
                }
            }
        }
        //Cas on la N és més petita que el tamany de correctword per tant s'ha de mirar
        //que el substring d'alphas siguin fins a tamany N
        else {
            ArrayList<String> alphas =new ArrayList<String>();
            ArrayList<String> betas =new ArrayList<String>();
            alphas = getAlphas(N,correctword);
            betas.add("");
            String palabra;
            for (int i = 1; i <= incorrectword.length(); ++i) {
                palabra = incorrectword.substring(0, i);
                matrixsProbability(N, palabra, alphas, betas, matrixtemp, matrixpair);
                betas = getBetas(palabra);
                matrixsProbability(N, palabra, alphas, betas, matrixtemp, matrixpair);
                betas.clear();
            }
        }
        //Es comprova que hi hagi alguna probabilitat introduida a la columna
        //Servirà per optimitzar el cami, si no supera el limit l'acumulador
        //de probabilitat no mereix la pena seguir avançant per aquella branca
        accumulator = 0;
        float limit = Constants.getGAMMA();
        for (int i = 0; i <matrixtemp.length; ++i ) {
            accumulator += matrixtemp[i][N];
        }
        if(accumulator > limit) {
            //S'ha superat el llindar limit
            //Es 'shifta' la matriu de probabilitats per optimitzar la matriu
            for(int i = 0; i < matrixtemp.length; ++i) {
                for(int j = 0; j < matrixtemp[0].length-1; ++j) {
                    matrixtemp[i][j] = matrixtemp[i][j+1];
                }
                matrixtemp[i][N] = (float) 0;
            }
            //Es 'shifta' la matriu de normes per optimitzar la matriu
            for(int i = 0; i < matrixpair.length; ++i) {
               for (int j = 0; j < matrixpair[0].length-1; ++j) {
                   arrstr2.clear();
                   arrstr2.addAll(matrixpair[i][j+1].getParam());
                   matrixpair[i][j].setParam(arrstr2);
               }
               matrixpair[i][N].getParam().clear();
            }
            arrstr2.clear();
            //Es comprova si el node on estem conté el final d'una paraula correcta i
            //si la matriu ens indica que canviar tota la paraula incorrecta (arribar
            //a l'última fila dóna una probabilitat) llavors es guarda la paraula,
            //la seva probabilitat i la llista de normes
            if(current.isFinal() && matrixtemp[incorrectword.length()][N-1] != 0) {
                Three<String, Float, ArrayList<Pair<String, String>>> pr = new Three<String, Float, ArrayList<Pair<String, String>>>();
                pr.correctWord = correctword;
                pr.probability = matrixtemp[incorrectword.length()][N-1];
                arrstr2.clear();
                arrstr2 = matrixpair[incorrectword.length()][N-1].getParam();
                pr.rules = new ArrayList<Pair<String, String>>();
                pr.rules.addAll(arrstr2);
                wordprob.add(pr);
               }
            //S'obtenen tots els fills del node actual i es recorren per buscar
            //més paraules correctes
            ArrayList<Trie<Matrix>> sons = new ArrayList<Trie<Matrix>>();
            sons = current.getChildTries();
            Iterator son = sons.listIterator();
            while(son.hasNext()) {
                //S'inicialitzen les matrius i es copien del pare
                float copia [][] = new float[incorrectword.length()+1][N+1];
                Element[][] matrixpaircopy = new Element[incorrectword.length()+1][N+1];
                for (int i = 0; i < incorrectword.length()+1; i++) {
                    for (int j = 0; j < N+1; j++) matrixpaircopy[i][j] = new Element();
                }
                for (int m = 0; m < copia.length; ++m) {
                    for (int n = 0; n < copia[0].length; ++n) {
                        copia[m][n] = matrixtemp[m][n];
                        matrixpaircopy[m][n].setParam(matrixpair[m][n].getParam());
                    }
                }
                //Es crida el fill amb les noves matrius
                auxiliar = getCorrect((Trie<Matrix>) son.next(), incorrectword, N, correctword, copia, matrixpaircopy);
                //Es guarda el resultat a wordprob
                wordprob.addAll(auxiliar);
            }
            if( !son.hasNext() ){
               //Quan s'ha recorregut tots els fills es retorna el wordprob acumulat
               return wordprob;
            }
        }
        //Si no es supera el llindar el programa retorna un cas buit
        ArrayList<Three<String, Float, ArrayList<Pair<String, String>>>> wordprob2 = new ArrayList<Three<String, Float, ArrayList<Pair<String, String>>>>();
        triplet.rules = new ArrayList<Pair<String, String>>();
        triplet.correctWord = "";
        triplet.probability = (float) 0;
        wordprob2.add(triplet);
        return wordprob2;
    }

    /**
     * Elimina de la llista els casos buits que hi poden aparéixer durant
     * l'execució del codi
     *
     * @param rubbish la llista de Three que pot contenir casos buits
     * @return llista de Three sense casos buits
     */
     private ArrayList<Three<String, Float, ArrayList<Pair<String, String>>>> takeWhite(ArrayList<Three<String, Float, ArrayList<Pair<String, String>>>> rubbish) {
        ArrayList<Three<String, Float, ArrayList<Pair<String, String>>>> cleaned = new ArrayList<Three<String, Float, ArrayList<Pair<String, String>>>>();
        for(Three<String, Float, ArrayList<Pair<String, String>>> nonwhite: rubbish) {
            if(!nonwhite.correctWord.equals("")) cleaned.add(nonwhite);
        }
        return cleaned;
     }


     /**
      * Aquesta funció cerca, utilitzant el diccionari i aplicant les normes
      * del model, les paraules més probables a ser canviades per la paraula
      * errònea word
      *
      * @param word és la paraula incorrecta
      * @return una llista de Three amb les paraules més probables i les
      * seves llistes de normes la qual han arribat de la paraula correcta
      * a la errònea
      */

    protected ArrayList<Three<String, Float, ArrayList<Pair<String, String>>>> getCorrectList(String word) {
        //S'inicialitza els paràmetres per la búsqueda
        ArrayList<Three<String, Float, ArrayList<Pair<String, String>>>> _list = new ArrayList<Three<String, Float, ArrayList<Pair<String, String>>>>();
        int N = Constants.getN();
        int len = word.length();
        String correctword = "";
        float matrixtemp[][] = new float[len+1][N+1];
        Element[][] matrixpair = new Element[word.length()+1][N+1];
        for (int i = 0; i < word.length()+1; i++) {
            for (int j = 0; j < N+1; j++) matrixpair[i][j] = new Element();
        }
        //Crida a la funció per la búsqueda de les paraules correctes
        _list = getCorrect(_dictionary, word, N, correctword, matrixtemp, matrixpair);
        //Neteja la sortida
        ArrayList<Three<String, Float, ArrayList<Pair<String, String>>>> _list2 = new ArrayList<Three<String, Float, ArrayList<Pair<String, String>>>>();
        ArrayList<Three<String, Float, ArrayList<Pair<String, String>>>> _list3 = new ArrayList<Three<String, Float, ArrayList<Pair<String, String>>>>();
        _list2.addAll(takeWhite(_list));
        if(!_list2.isEmpty()) {
            _list3.addAll(mostProbabilityPair(_list2));
        }
        //Retorna el resultat en forma de llista
        return _list3;
    }

    /**
     * Ordena descendentment, aplicant l'algoritme merge-sort, la llista de
     * Three , que conté un String, un float i una llista de Pairs d'String,
     * segons el float que conté la probabilitat.
     *
     * @param list és la llista no ordenada de Three
     * @param left és esquerra index que et marca la possició més de l'esquerra
     * @param right és dreta índex que et marca la possició més a la dreta
     * @return la llista ordenada descendentment de Three
     */
    private ArrayList<Three<String, Float, ArrayList<Pair<String, String>>>> merge(ArrayList<Three<String, Float, ArrayList<Pair<String, String>>>> list, int left, int right) {
        //Algoritme MERGE-SORT
        ArrayList<Three<String, Float, ArrayList<Pair<String, String>>>> sorted = new ArrayList<Three<String, Float, ArrayList<Pair<String, String>>>>();
        if (right == left) {
            sorted.add(list.get(right));
            return sorted;
        }
        ArrayList<Three<String, Float, ArrayList<Pair<String, String>>>> list_left = merge(list, left, left + (right - left) / 2);
        ArrayList<Three<String, Float, ArrayList<Pair<String, String>>>> list_right = merge(list, left + ((right - left) / 2) + 1, right);

        int leftposition = 0;
        int rightposition = 0;

        while(leftposition < list_left.size()  && rightposition < list_right.size()) {
            if(list_left.get(leftposition).probability > list_right.get(rightposition).probability) sorted.add(list_left.get(leftposition++));
            else sorted.add(list_right.get(rightposition++));
        }
        while(leftposition < list_left.size()) sorted.add(list_left.get(leftposition++));
        while(rightposition < list_right.size()) sorted.add(list_right.get(rightposition++));
        return sorted;
    }


    /**
     * Selecciona de la llista de Three els més probables, el número del
     * qual es donat per SUGGESTIONS
     *
     * @param list és una llista de Three amb totes les alphas possibles
     * que pot tenir beta.
     * @return una llista de Three amb els més probables, el número del
     * qual es donat per SUGGESTIONS
     */
    private ArrayList<Three<String, Float, ArrayList<Pair<String, String>>>> mostProbabilityPair(ArrayList<Three<String, Float, ArrayList<Pair<String, String>>>> list) {
        //Inicialitza la llista que retornarà
        ArrayList<Three<String, Float, ArrayList<Pair<String, String>>>> aux = new ArrayList<Three<String, Float, ArrayList<Pair<String, String>>>>();
        Three<String, Float, ArrayList<Pair<String, String>>> element = new Three<String, Float, ArrayList<Pair<String, String>>>();
        //Ordena la llista en ordre descendent per probabilitats
        aux.addAll(merge(list, 0, list.size()-1));
        //Es fica en la llista auxiliar els Three primers (donat per getSUGGESTIONS)
        ArrayList<Three<String, Float, ArrayList<Pair<String, String>>>> auxiliar =new ArrayList<Three<String, Float, ArrayList<Pair<String, String>>>>();
        int i = 0;
        Iterator secondlist = aux.iterator();
        while(secondlist.hasNext() && i < Constants.getSUGGESTIONS()) {
            element = (Three<String, Float, ArrayList<Pair<String, String>>>) secondlist.next();
            auxiliar.add(i, element);
            ++i;
        }
        //Retorna els Three suggerits
        return auxiliar;
    }


    @Override
    protected void addWord(String word) {
        Matrix mat = new Matrix();
        ++_numofwords;
        _dictionary.put(word, mat);
    }

    @Override
    protected void deleteWord(String word) {
        --_numofwords;
        _dictionary.delete(word);
    }

    @Override
    protected boolean isFound(String word) {
        return _dictionary.exists(word);
    }

    @Override
    protected int getNumOfWords() {
        return _numofwords;
    }
}

